Often, the size of a digital image stored on one device may need to be reduced in order for the image to be stored or displayed on a different device. For example, a large, high-quality digital image stored on a server may exceed the memory limitations of a mobile device. In order for the mobile device to store and display the image, it would be necessary to reduce the size of the previously compressed image.
If memory capacity were the only limitation, it would be possible to devise an algorithm to reduce the image size as the image is received (prior to storage), rather than reducing the size prior to transmission. However, in reality, other limitations also apply. For example, some protocols limit the maximum message size that can be transmitted to the mobile device. In that case, the image size must be reduced prior to (not after) transmission. Additionally, even when the maximum message size is sufficient to accommodate the image, reducing image size on the receiving end may waste significant bandwidth, resulting in cost inefficiencies.
Furthermore, because processing time is directly related to how many images per second an operator can handle, there is a clear economic relationship between the time taken to reduce an image and the cost of doing so. Such a relationship exists for multimedia messaging services, motivating the need for an efficient size-reduction method. In this specification, “size” means the number of bytes utilized by the compressed image. Thus, a “large” image is one that occupies many bytes in a storage space.
In the past, palette-based compressed images were reduced using a brute-force approach, where the compressed image is partially decompressed by decoding it to yield palette index values. The partially decompressed image is re-quantized using an altered palette and recompressed repeatedly until the size of the re-compressed image meets a target size. As shown in FIG. 1, the brute-force approach usually involves many iterative steps. If the recompressed image is too large or too small as compared to the target size, the palette is readjusted and the palette indices are updated to reflect the new palette. This brute-force approach, in general, is time-consuming due to the repeated compression. In the above-described method, the repeated compression is terminated when the size of the recompressed image meets the target size. Alternatively, the repeated compression can be terminated when the quality of the recompressed image reaches an unacceptable level. In this alternative approach, a palette is selected to meet a target number of palette colors, and an output image is produced based on the selected palette so as to allow a user to judge whether the quality of the output image is acceptable. This approach requires the input of a user and, therefore, is unsuitable for an image-related application in an automated environment.
It should be noted that image size reduction could also be achieved by decreasing the image resolution or by changing the compression format. However, resolution reduction may not always be desirable in that it may not yield acceptable image quality. While format conversion may produce images of comparable quality, it may not result in a smaller image size. Because palette-based schemes are almost always followed by lossless compression, such as in the GIF format, there is no scope for reducing the size of the image after a palette has been developed. When a compressed image in the GIF format is converted to the JPEG format, for example, the size of the converted image may actually increase.
Most previous work with image palettes is concerned with mapping true color (RGB) values of an image onto a finite-size palette, or mapping one palette to another palette. The former approach, which is generally associated with a display device, has been disclosed in Shibata et al. (JP07-037059). The latter approach, which is used when the size of the new palette is known but the palette content may be unknown, has been disclosed in Okuda et al. (JP11-306067). Although these approaches can reduce colors of an image to achieve a certain palette size, they may or may not lead to size reduction. Moreover, the amount of image size reduction cannot be predicted or controlled.
It is desirable and advantageous to provide a method and device for image size reduction wherein the iterative steps can be reduced both in number and in complexity, and wherein the amount of image size reduction can be estimated and controlled.